Le système RSA

Le système RSA (le nom vient des trois créateurs du système : Rivest, Shamir et Adelman - 1978) est un système cryptographique à clé publique basé sur la difficulté de factoriser des grands nombres entiers.

Protocole du RSA

• Le destinataire \(\text B\) choisit deux nombres premiers distincts \(p\) et \(q\) .
  Il calcule \(N=pq\) et \(n=(p-1)(q-1)\) .
  Il choisit ensuite un entier \(c\) tel que \(1 \leqslant c et \(\mathrm{PGCD}(c;n)=1\) .
  Il calcule alors l'unique entier \(d\) tel que \(1 \leqslant d et \(cd \equiv 1 \ [n]\) .
  
• Le destinataire \(\text B\)
  - diffuse sa clé publique constituée des entiers \(N\) et \(c\) ;
  - garde secrets les entiers \(p\) , \(q\) et \(d\) .
  
• L'expéditeur \(\text A\) convertit son message en une suite de nombres inférieurs à \(N\) .
  Pour coder un nombre \(a\) , l'expéditeur calcule \(b\) tel que \(a^c \equiv b \ [N]\) et transmet le nombre \(b\) au destinataire.
  
• Pour décoder un nombre \(b\) , le destinataire calcule \(b'\) tel que \(b^d \equiv b' \ [N]\) ,
  c'est-à-dire \(a^{cd} \equiv b' \ [N]\) .
  Il associe ensuite au nombre \(b\) la lettre de rang \(b'\) dans l'alphabet.